{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #数组中两个数的最大异或值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #trie #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #字典树 #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMaximumXOR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组中两个数的最大异或值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组 <code>nums</code> ，返回<em> </em><code>nums[i] XOR nums[j]</code> 的最大运算结果，其中 <code>0 &le; i &le; j &lt; n</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,10,5,25,2,8]\n",
    "<strong>输出：</strong>28\n",
    "<strong>解释：</strong>最大运算结果是 5 XOR 25 = 28.</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,4]\n",
    "<strong>输出：</strong>6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [8,10,2]\n",
    "<strong>输出：</strong>10\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [14,70,53,83,49,91,36,80,92,51,66,70]\n",
    "<strong>输出：</strong>127\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你可以在 <code>O(n)</code> 的时间解决这个问题吗？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 421&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/\">https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ms70jA](https://leetcode.cn/problems/ms70jA/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ms70jA](https://leetcode.cn/problems/ms70jA/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,10,5,25,2,8]', '[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        HIGH_BIT = 31\n",
    "        x = 0\n",
    "        for pos in range(HIGH_BIT-1,-1,-1):\n",
    "            x = 2 * x + 1\n",
    "            seen = set()\n",
    "            for num in nums:\n",
    "                seen.add(num >> pos)\n",
    "            found = False\n",
    "            for num in nums:\n",
    "                val = num >> pos ^ x\n",
    "                if val in seen:\n",
    "                    found = True\n",
    "                    break\n",
    "            if not found:\n",
    "                x -= 1\n",
    "        return x\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        x = 0\n",
    "        k = 31\n",
    "        while k >= 0:\n",
    "            prefix = set()\n",
    "            for num in nums:\n",
    "                prefix.add(num>>k)\n",
    "            x <<= 1\n",
    "            x += 1\n",
    "            found = False\n",
    "            for num in nums:\n",
    "                if (num>>k) ^ x in prefix:\n",
    "                    found = True\n",
    "                    break\n",
    "            \n",
    "            if not found:\n",
    "                x -= 1\n",
    "\n",
    "            k -= 1\n",
    "\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        x = 0\n",
    "        for i in range(31, -1,-1):\n",
    "            seen = set()\n",
    "            for n in nums:\n",
    "                seen.add(n >> i)\n",
    "            \n",
    "            nextx = x * 2 + 1\n",
    "            \n",
    "            found = False\n",
    "            for n in nums:\n",
    "                if nextx ^ (n >> i) in seen:\n",
    "                    found = True\n",
    "                    break\n",
    "            \n",
    "            if not found:\n",
    "                nextx -= 1\n",
    "            \n",
    "            x = nextx\n",
    "        \n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        HIGH_BIT = 30\n",
    "\n",
    "        x = 0\n",
    "        for k in range(HIGH_BIT, -1, -1):\n",
    "            seen = set()\n",
    "\n",
    "            for num in nums:\n",
    "                seen.add(num >> k)\n",
    "\n",
    "            x_next = x * 2 + 1\n",
    "            found = False\n",
    "\n",
    "            for num in nums:\n",
    "                if x_next ^ (num >> k) in seen:\n",
    "                    found = True\n",
    "                    break\n",
    "\n",
    "            if found:\n",
    "                x = x_next\n",
    "            else:\n",
    "                x = x_next - 1\n",
    "        \n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        method = 'leetcode'\n",
    "        if method == 'leetcode':\n",
    "            high_bit = 30\n",
    "            x = 0\n",
    "            for k in range(high_bit, -1, -1):\n",
    "                seen = set()\n",
    "\n",
    "                for num in nums:\n",
    "                    seen.add(num >> k)\n",
    "\n",
    "                x_next = x * 2 + 1\n",
    "                found = False\n",
    "\n",
    "                for num in nums:\n",
    "                    if x_next ^ (num >> k) in seen:\n",
    "                        found = True\n",
    "                        break\n",
    "\n",
    "                if found:\n",
    "                    x = x_next\n",
    "                else:\n",
    "                    x = x_next - 1\n",
    "            return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        mask = 0\n",
    "        ans = 0\n",
    "        for i in range(30, -1, -1):\n",
    "            mask |= 1 << i\n",
    "            s = set()\n",
    "            for j in nums:\n",
    "                s.add(mask & j)\n",
    "            target = ans | (1 << i)\n",
    "            for j in s:\n",
    "                if j ^ target in s:\n",
    "                    ans = target\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        # n = len(nums)\n",
    "        # ans = 0\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i+1,n):\n",
    "        #         ans = max(ans,nums[i]^nums[j])\n",
    "        # return ans\n",
    "        ans = mask = 0\n",
    "        hight_bit = max(nums).bit_length() -1#用1与的时后,已经有一个1\n",
    "\n",
    "        for i in range(hight_bit,-1,-1):\n",
    "            mask |= 1<<i\n",
    "\n",
    "            newans = ans|1<<i  \n",
    "\n",
    "            seen = set()  \n",
    "\n",
    "            for x in nums:\n",
    "                x &= mask \n",
    "\n",
    "                if newans^x in seen:\n",
    "                    ans = newans\n",
    "                    break\n",
    "                seen.add(x)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        ans = mask = 0\n",
    "        mx_bit = max(nums).bit_length() - 1\n",
    "        for bit in range(mx_bit, -1, -1):\n",
    "            mask |= 1 << bit\n",
    "            new_ans = ans | (1 << bit)\n",
    "            seen = set()\n",
    "            for x in nums:\n",
    "                x &= mask\n",
    "                if new_ans ^ x in seen:\n",
    "                    ans = new_ans\n",
    "                    break\n",
    "                seen.add(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        HIGHT_BIT = 30\n",
    "        x = 0\n",
    "        for k in range(HIGHT_BIT, -1, -1):\n",
    "            seen = set()\n",
    "            for num in nums:\n",
    "                seen.add(num>>k)\n",
    "            x_next = x*2+1\n",
    "            found = False\n",
    "            for num in nums:\n",
    "                if x_next ^(num>>k) in seen:\n",
    "                    found = True\n",
    "                    break\n",
    "            if found:\n",
    "                x = x_next\n",
    "            else:\n",
    "                x = x_next-1\n",
    "        return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        highBit = 30\n",
    "        \n",
    "        x = 0\n",
    "        for b in range(highBit, -1, -1):\n",
    "            visited = set()\n",
    "            \n",
    "            for v  in nums:\n",
    "                visited.add(v>>b)\n",
    "            \n",
    "            xNew = x * 2 + 1\n",
    "            \n",
    "            find = 0\n",
    "            \n",
    "            for v in nums:\n",
    "                if xNew ^ (v >> b) in visited:\n",
    "                    find = 1\n",
    "                    break\n",
    "            if find:\n",
    "                x = xNew\n",
    "            else:\n",
    "                x = xNew - 1\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        HIGH_BIT = 30\n",
    "        x = 0\n",
    "        for k in range(HIGH_BIT,-1,-1):\n",
    "            seen = set()\n",
    "            for num in nums:\n",
    "                seen.add(num>>k)\n",
    "            x_next = 2*x+1\n",
    "            found =False\n",
    "            for num in nums:\n",
    "                if x_next^(num>>k) in seen:\n",
    "                    found = True\n",
    "                    break\n",
    "            if found:\n",
    "                x = x_next\n",
    "            else:\n",
    "                x = x_next-1\n",
    "        return x\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        HIGH_BIT = 30\n",
    "\n",
    "        x = 0\n",
    "        for k in range(HIGH_BIT, -1, -1):\n",
    "            seen = set()\n",
    "            for num in nums:\n",
    "                seen.add(num >> k)\n",
    "\n",
    "            x_next = x * 2 + 1\n",
    "            found = False\n",
    "            \n",
    "            for num in nums:\n",
    "                if x_next ^ (num >> k) in seen:\n",
    "                    found = True\n",
    "                    break\n",
    "\n",
    "            if found:\n",
    "                x = x_next\n",
    "            else:\n",
    "                x = x_next - 1\n",
    "        \n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        #贪心思想+哈希表,尝试着每一位分配1,从高到低分配\n",
    "        res=mask=0\n",
    "        for i in range(30,-1,-1):\n",
    "            mask|=1<<i\n",
    "            s=set()\n",
    "            for num in nums:\n",
    "                s.add(num&mask)\n",
    "            tmp=res|(1<<i)\n",
    "            for j in s:\n",
    "                if tmp^j in s:\n",
    "                    res=tmp\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        HIGH_BIT = 30\n",
    "        x = 0\n",
    "        for k in range(HIGH_BIT, -1, -1):\n",
    "            seen = set()\n",
    "            for num in nums:\n",
    "                seen.add(num >> k)\n",
    "            x_next = 2 * x + 1\n",
    "            found = False\n",
    "            for num in nums:\n",
    "                if x_next ^ (num >> k) in seen:\n",
    "                    found = True\n",
    "                    break\n",
    "            if found:\n",
    "                x = x_next\n",
    "            else:\n",
    "                x = x_next - 1\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        #贪心思想+哈希表,尝试着每一位分配1,从高到低分配\n",
    "        res=mask=0\n",
    "        for i in range(30,-1,-1):\n",
    "            mask|=1<<i\n",
    "            s=set()\n",
    "            for num in nums:\n",
    "                s.add(num&mask)\n",
    "            #尝试将结果的这一位置为1\n",
    "            tmp=res|(1<<i)\n",
    "            for j in s:\n",
    "                if tmp^j in s:\n",
    "                    res=tmp\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        High_Bit = 30\n",
    "\n",
    "        x = 0\n",
    "        for i in range(High_Bit, -1, -1):\n",
    "            seen = set()\n",
    "\n",
    "            for num in nums:\n",
    "                seen.add(num >> i)\n",
    "            \n",
    "            x_next = x * 2 + 1\n",
    "            found = False\n",
    "            for num in nums:\n",
    "                \n",
    "                if x_next ^ (num >> i) in seen:\n",
    "                    found = True\n",
    "                    break\n",
    "            \n",
    "            if found:\n",
    "                x = x_next\n",
    "            else:\n",
    "                x = x_next - 1\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        res, mask = 0, 0\n",
    "        for i in range(30, -1, -1):\n",
    "            mask |= (1 << i)\n",
    "\n",
    "            s = set()\n",
    "            for num in nums:\n",
    "                s.add(mask & num)\n",
    "            \n",
    "            tmp = res | (1 << i)\n",
    "            for p in s:\n",
    "                if tmp ^ p in s:\n",
    "                    res = tmp\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        HIGH_BIT = 30\n",
    "        x = 0\n",
    "        for k in range(HIGH_BIT, -1, -1):\n",
    "            seen = set()\n",
    "            for num in nums:\n",
    "                seen.add(num >> k)\n",
    "            x_next = x * 2 + 1\n",
    "            found = False\n",
    "            for num in nums:\n",
    "                if x_next ^ (num >> k) in seen:\n",
    "                    found = True\n",
    "                    break\n",
    "            if found:\n",
    "                x = x_next\n",
    "            else:\n",
    "                x = x_next - 1\n",
    "        return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        m = 0  \n",
    "        for j in range(32)[::-1]:\n",
    "            m|=(1<<j)\n",
    "            t = [m&i for i in nums]\n",
    "            s = set()\n",
    "            for i in t:\n",
    "                if i in s:\n",
    "                    break \n",
    "                s.add(m^i)\n",
    "            else:\n",
    "                m -= (1<<j)\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        # 左子树指向表示 0 的子节点\n",
    "        self.left = None\n",
    "        # 右子树指向表示 1 的子节点\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        # 字典树的根节点\n",
    "        root = Trie()\n",
    "        # 最高位的二进制位编号为 30\n",
    "        HIGH_BIT = 30\n",
    "\n",
    "        def add(num: int):\n",
    "            cur = root\n",
    "            for k in range(HIGH_BIT, -1, -1):\n",
    "                bit = (num >> k) & 1\n",
    "                if bit == 0:\n",
    "                    if not cur.left:\n",
    "                        cur.left = Trie()\n",
    "                    cur = cur.left\n",
    "                else:\n",
    "                    if not cur.right:\n",
    "                        cur.right = Trie()\n",
    "                    cur = cur.right\n",
    "\n",
    "        def check(num: int) -> int:\n",
    "            cur = root\n",
    "            x = 0\n",
    "            for k in range(HIGH_BIT, -1, -1):\n",
    "                bit = (num >> k) & 1\n",
    "                if bit == 0:\n",
    "                    # a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走\n",
    "                    if cur.right:\n",
    "                        cur = cur.right\n",
    "                        x = x * 2 + 1\n",
    "                    else:\n",
    "                        cur = cur.left\n",
    "                        x = x * 2\n",
    "                else:\n",
    "                    # a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走\n",
    "                    if cur.left:\n",
    "                        cur = cur.left\n",
    "                        x = x * 2 + 1\n",
    "                    else:\n",
    "                        cur = cur.right\n",
    "                        x = x * 2\n",
    "            return x\n",
    "\n",
    "        n = len(nums)\n",
    "        x = 0\n",
    "        for i in range(1, n):\n",
    "            # 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中\n",
    "            add(nums[i - 1])\n",
    "            # 将 nums[i] 看作 ai，找出最大的 x 更新答案\n",
    "            x = max(x, check(nums[i]))\n",
    "\n",
    "        return x\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        # 左子树指向表示 0 的子节点\n",
    "        self.left = None\n",
    "        # 右子树指向表示 1 的子节点\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        # 字典树的根节点\n",
    "        root = Trie()\n",
    "        # 最高位的二进制位编号为 30\n",
    "        HIGH_BIT = 30\n",
    "\n",
    "        def add(num: int):\n",
    "            cur = root\n",
    "            for k in range(HIGH_BIT, -1, -1):\n",
    "                bit = (num >> k) & 1\n",
    "                if bit == 0:\n",
    "                    if not cur.left:\n",
    "                        cur.left = Trie()\n",
    "                    cur = cur.left\n",
    "                else:\n",
    "                    if not cur.right:\n",
    "                        cur.right = Trie()\n",
    "                    cur = cur.right\n",
    "\n",
    "        def check(num: int) -> int:\n",
    "            cur = root\n",
    "            x = 0\n",
    "            for k in range(HIGH_BIT, -1, -1):\n",
    "                bit = (num >> k) & 1\n",
    "                if bit == 0:\n",
    "                    # a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走\n",
    "                    if cur.right:\n",
    "                        cur = cur.right\n",
    "                        x = x * 2 + 1\n",
    "                    else:\n",
    "                        cur = cur.left\n",
    "                        x = x * 2\n",
    "                else:\n",
    "                    # a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走\n",
    "                    if cur.left:\n",
    "                        cur = cur.left\n",
    "                        x = x * 2 + 1\n",
    "                    else:\n",
    "                        cur = cur.right\n",
    "                        x = x * 2\n",
    "            return x\n",
    "\n",
    "        n = len(nums)\n",
    "        x = 0\n",
    "        for i in range(1, n):\n",
    "            # 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中\n",
    "            add(nums[i - 1])\n",
    "            # 将 nums[i] 看作 ai，找出最大的 x 更新答案\n",
    "            x = max(x, check(nums[i]))\n",
    "\n",
    "        return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.left = None # 0\n",
    "        self.right = None # 1\n",
    "    \n",
    "    def insert(self, num):\n",
    "        node = self\n",
    "        for i in range(30, -1, -1):\n",
    "            bit = (num >> i) &  1\n",
    "            if bit == 1:\n",
    "                if not node.right:\n",
    "                    node.right = Trie()\n",
    "                node = node.right\n",
    "            else:\n",
    "                if not node.left:\n",
    "                    node.left = Trie()\n",
    "                node = node.left\n",
    "    def findMax(self, num):\n",
    "        node = self\n",
    "        ans = 0\n",
    "        for i in range(30, -1, -1):\n",
    "            bit = (num >> i) & 1\n",
    "            if bit == 1:\n",
    "                if node.left:\n",
    "                    node = node.left\n",
    "                    ans = (ans<<1) + 1\n",
    "                else:\n",
    "                    node = node.right\n",
    "                    ans = ans<<1\n",
    "            else:\n",
    "                if node.right:\n",
    "                    node = node.right\n",
    "                    ans = (ans<<1) + 1\n",
    "                else:\n",
    "                    node = node.left\n",
    "                    ans = ans<<1\n",
    "        return ans\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        # 将数组内的数从高到低逐位插入到字典树里\n",
    "        if (len(nums)) == 0:\n",
    "            return 0\n",
    "        trie = Trie()\n",
    "        trie.insert(nums[0])\n",
    "        ans = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            ans = max(ans, trie.findMax(nums[i]))\n",
    "            trie.insert(nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self,val,left=None,right=None):\n",
    "        self.val = val\n",
    "        self.left=left\n",
    "        self.right = right\n",
    "\n",
    "class PrefixT:\n",
    "    def __init__(self):\n",
    "        self.root = Node(val=-1,left =None,right=None)\n",
    "        self.res = 0\n",
    "    def print(self,root):\n",
    "        if root==None:\n",
    "            return \"\"\n",
    "        # print(root)\n",
    "        s = \"[\"+str(root.val)+\"[\"+self.print(root.left)+\"]\"+\"[\"+self.print(root.right)+\"]\"\n",
    "        return s\n",
    "    def insert(self,num):\n",
    "        \n",
    "        r= self.root\n",
    "        \n",
    "        binary = [] \n",
    "        while num!=0:\n",
    "            add = num%2\n",
    "            num = num//2\n",
    "            binary.append(add)\n",
    "        binary = binary+[0]*(31-len(binary))\n",
    "        binary = binary[::-1]\n",
    "        #print(\"insert \", num,binary)\n",
    "        \n",
    "        tmp_res = 0\n",
    "        other_r = self.root\n",
    "        base = 1<<(len(binary)-1)\n",
    "        for b in binary:\n",
    "            if b==0:\n",
    "                if other_r and other_r.right:\n",
    "                    tmp_res += base\n",
    "                    other_r = other_r.right\n",
    "                elif other_r:\n",
    "                    other_r = other_r.left\n",
    "                else:\n",
    "                    pass\n",
    "                    \n",
    "                if r.left==None:\n",
    "                    r.left = Node(val=0,left = None,right =None)\n",
    "                r = r.left\n",
    "            else:\n",
    "                if other_r  and other_r.left:\n",
    "                    tmp_res += base\n",
    "                    other_r =other_r.left\n",
    "                elif other_r:\n",
    "                    other_r = other_r.right\n",
    "                else:\n",
    "                    pass    \n",
    "                \n",
    "                if r.right ==None:\n",
    "                    r.right = Node(val = 1,left =None,right =None)\n",
    "                r = r.right\n",
    "            base =base>>1\n",
    "        # s = self.print(self.root)\n",
    "        # print(s)\n",
    "        \n",
    "        \n",
    "        \n",
    "        return tmp_res\n",
    "        \n",
    "        \n",
    "        \n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        \n",
    "        prefixT = PrefixT()\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            tmp_res = prefixT.insert(num)\n",
    "            res = max(res,tmp_res)\n",
    "            \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "\n",
    "    def __init__(self) -> None:\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self) -> None:\n",
    "        self.root = TreeNode()\n",
    "\n",
    "    def num2str(self, num):\n",
    "        ans = ''\n",
    "        for _ in range(32):\n",
    "            ans += '1' if num % 2 else '0'\n",
    "            num = num >> 1\n",
    "        return ans[::-1]\n",
    "    \n",
    "    def insert(self, s):\n",
    "        cur = self.root\n",
    "        for i in range(32):\n",
    "            if s[i] == '0':\n",
    "                if not cur.left:\n",
    "                    cur.left = TreeNode()\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                if not cur.right:\n",
    "                    cur.right = TreeNode()\n",
    "                cur = cur.right\n",
    "\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        strs = [self.num2str(num) for num in nums]\n",
    "        for i in range(n):\n",
    "            self.insert(strs[i])\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            s = strs[i]\n",
    "            cur = self.root\n",
    "            t = 0\n",
    "            for i in range(32):\n",
    "                if s[i] == '0':\n",
    "                    if cur.right:\n",
    "                        cur = cur.right\n",
    "                        t = (t << 1) + 1\n",
    "                    else:\n",
    "                        cur = cur.left\n",
    "                        t = (t << 1) + 0\n",
    "                else:\n",
    "                    if cur.left:\n",
    "                        cur = cur.left\n",
    "                        t = (t << 1) + 1\n",
    "                    else:\n",
    "                        cur = cur.right\n",
    "                        t = (t << 1) + 0\n",
    "            ans = max(ans, t)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class xor_tree:\n",
    "    def __init__(self, left = None, right=None):\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        d = {}\n",
    "        def add(num):\n",
    "            cur = d\n",
    "            for i in range(30, -1, -1):\n",
    "                n = (num >> i) & 1\n",
    "                if n not in cur:\n",
    "                    cur[n] = {}\n",
    "                cur = cur[n]\n",
    "        \n",
    "        def check(num):\n",
    "            cur = d\n",
    "            ans = 0\n",
    "            for i in range(30, -1, -1):\n",
    "                n = (num >> i) & 1\n",
    "                if 1 - n in cur:\n",
    "                    ans += pow(2, i)\n",
    "                    cur = cur[1 - n]\n",
    "                else:\n",
    "                    cur = cur[n]\n",
    "            return ans\n",
    "        \n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        if n < 2:\n",
    "            return ans\n",
    "        add(nums[0])\n",
    "        for i in range(1, n):\n",
    "            add(nums[i])\n",
    "            ans = max(ans, check(nums[i]))\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        trie = {}\n",
    "        ret = 0\n",
    "        for num in nums:\n",
    "            cur = trie\n",
    "            search = trie\n",
    "            temp = 0\n",
    "\n",
    "            for i in range(30, -1, -1):\n",
    "                b = num >> i & 1\n",
    "                p = b ^ 1\n",
    "                if b not in cur:\n",
    "                    cur[b] = {}\n",
    "                cur = cur[b]\n",
    "                if p in search:\n",
    "                    search = search[p]\n",
    "                    temp = temp * 2 + 1\n",
    "                else:\n",
    "                    search = search[b]\n",
    "                    temp = temp * 2\n",
    "            \n",
    "            ret = max(ret, temp)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class BinaryTrie:\n",
    "    def __init__(self) -> None:\n",
    "        self.kids = [None, None]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        binary_trie = {}\n",
    "        max_xor = 0\n",
    "        max_num = max(nums)\n",
    "        if max_num == 0:\n",
    "            return 0\n",
    "        max_bit = int(math.log2(max_num)) + 2\n",
    "        bits=[0]*max_bit\n",
    "        for i in range(len(nums)):\n",
    "            temp = nums[i]\n",
    "            # bits = [0] * max_bit\n",
    "            for j in range(max_bit):\n",
    "                bits[j] = temp % 2\n",
    "                temp //= 2\n",
    "                # if temp == 0:\n",
    "                #     break\n",
    "            temp = binary_trie\n",
    "            temp_xor = 0\n",
    "            for j in range(max_bit - 1, -1, -1):\n",
    "                if 1-bits[j] in temp:\n",
    "                    temp_xor+=1<<j\n",
    "                    temp=temp[1-bits[j]]\n",
    "                elif bits[j] in temp:\n",
    "                    temp = temp[bits[j]]\n",
    "                else:\n",
    "                    break\n",
    "            max_xor = max(max_xor, temp_xor)\n",
    "            temp = binary_trie\n",
    "            for j in range(max_bit - 1, -1, -1):\n",
    "                if bits[j] not in temp:\n",
    "                    temp[bits[j]] = {}\n",
    "                temp = temp[bits[j]]\n",
    "        return max_xor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        if not nums: return 0\n",
    "        root = {}\n",
    "        for num in nums:\n",
    "            cur = root\n",
    "            for i in range(31, -1, -1):\n",
    "                cur_bit = (num >> i) & 1 # 右移\n",
    "                # cur[cur_bit] = {} # 直接覆盖 ❌\n",
    "                cur.setdefault(cur_bit, {}) # key不存在才会赋值, key存在保持原数据不变\n",
    "                cur = cur[cur_bit]\n",
    "        res = -float('inf')\n",
    "        for num in nums:\n",
    "            cur = root\n",
    "            cur_max = 0\n",
    "            for i in range(31, -1, -1):\n",
    "                cur_bit = (num >> i) & 1\n",
    "                if (cur_bit ^ 1) in cur:\n",
    "                   cur_max += (1 << i)\n",
    "                   cur = cur[cur_bit ^ 1]\n",
    "                else: \n",
    "                    cur = cur[cur_bit]\n",
    "            res = max(res, cur_max)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        x = max(nums)\n",
    "        class tire:\n",
    "            def __init__(self):\n",
    "                self.next=[None]*2\n",
    "                self.p = 0\n",
    "                self.e = 0\n",
    "            \n",
    "            def insert(self,next_num:int):\n",
    "\n",
    "                self.p += 1\n",
    "                if self.next[next_num] is None:\n",
    "                    self.next[next_num] = tire()\n",
    "                return self.next[next_num]\n",
    "\n",
    "\n",
    "            def find(self,next_num:int)->int:\n",
    "                if self.next[next_num] is None:\n",
    "                    return False\n",
    "                return True\n",
    "        root = tire()\n",
    "        for n in nums:\n",
    "            b = 30\n",
    "            p = root\n",
    "            while b >= 0:\n",
    "                p = p.insert((n >> b) & 1)\n",
    "                b-=1\n",
    "            p.e += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for n in nums:\n",
    "            b = 30\n",
    "            t = 0\n",
    "            i = root\n",
    "            while b >= 0:\n",
    "                if (n >> b) & 1:\n",
    "                    if i.find(0):\n",
    "                        t = (t<<1)+1\n",
    "                        i = i.next[0]\n",
    "                    else:\n",
    "                        t = t << 1\n",
    "                        i = i.next[1]\n",
    "                else:\n",
    "                    if i.find(1):\n",
    "                        t = (t<<1)+1\n",
    "                        i = i.next[1]\n",
    "                    else:\n",
    "                        t = t<<1\n",
    "                        i = i.next[0]\n",
    "                b -= 1\n",
    "\n",
    "            ans = max(ans,t)\n",
    "\n",
    "\n",
    "\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        x = max(nums)\n",
    "        ba = 0\n",
    "        for n in nums:\n",
    "            bn = 31\n",
    "            while n >> bn and bn >= 0:\n",
    "                bn -= 1\n",
    "            ba = max(bn,ba)\n",
    "        class tire:\n",
    "            def __init__(self):\n",
    "                self.next=[None]*2\n",
    "                self.p = 0\n",
    "                self.e = 0\n",
    "            \n",
    "            def insert(self,next_num:int):\n",
    "\n",
    "                self.p += 1\n",
    "                if self.next[next_num] is None:\n",
    "                    self.next[next_num] = tire()\n",
    "                return self.next[next_num]\n",
    "\n",
    "\n",
    "            def find(self,next_num:int)->int:\n",
    "                if self.next[next_num] is None:\n",
    "                    return False\n",
    "                return True\n",
    "        root = tire()\n",
    "        for n in nums:\n",
    "            b = ba\n",
    "            p = root\n",
    "            while b >= 0:\n",
    "                p = p.insert((n >> b) & 1)\n",
    "                b-=1\n",
    "            p.e += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for n in nums:\n",
    "            b = ba\n",
    "            t = 0\n",
    "            i = root\n",
    "            while b >= 0:\n",
    "                if (n >> b) & 1:\n",
    "                    if i.find(0):\n",
    "                        t = (t<<1)+1\n",
    "                        i = i.next[0]\n",
    "                    else:\n",
    "                        t = t << 1\n",
    "                        i = i.next[1]\n",
    "                else:\n",
    "                    if i.find(1):\n",
    "                        t = (t<<1)+1\n",
    "                        i = i.next[1]\n",
    "                    else:\n",
    "                        t = t<<1\n",
    "                        i = i.next[0]\n",
    "                b -= 1\n",
    "\n",
    "            ans = max(ans,t)\n",
    "\n",
    "\n",
    "\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        x = max(nums)\n",
    "        bn = 31\n",
    "        while x >> bn:\n",
    "                bn -= 1\n",
    "        ba = bn\n",
    "        class tire:\n",
    "            def __init__(self):\n",
    "                self.next=[None]*2\n",
    "                self.p = 0\n",
    "                self.e = 0\n",
    "            \n",
    "            def insert(self,next_num:int):\n",
    "\n",
    "                self.p += 1\n",
    "                if self.next[next_num] is None:\n",
    "                    self.next[next_num] = tire()\n",
    "                return self.next[next_num]\n",
    "\n",
    "\n",
    "            def find(self,next_num:int)->int:\n",
    "                if self.next[next_num] is None:\n",
    "                    return False\n",
    "                return True\n",
    "        root = tire()\n",
    "        for n in nums:\n",
    "            b = ba\n",
    "            p = root\n",
    "            while b >= 0:\n",
    "                p = p.insert((n >> b) & 1)\n",
    "                b-=1\n",
    "            p.e += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for n in nums:\n",
    "            b = ba\n",
    "            t = 0\n",
    "            i = root\n",
    "            while b >= 0:\n",
    "                if (n >> b) & 1:\n",
    "                    if i.find(0):\n",
    "                        t = (t<<1)+1\n",
    "                        i = i.next[0]\n",
    "                    else:\n",
    "                        t = t << 1\n",
    "                        i = i.next[1]\n",
    "                else:\n",
    "                    if i.find(1):\n",
    "                        t = (t<<1)+1\n",
    "                        i = i.next[1]\n",
    "                    else:\n",
    "                        t = t<<1\n",
    "                        i = i.next[0]\n",
    "                b -= 1\n",
    "\n",
    "            ans = max(ans,t)\n",
    "\n",
    "\n",
    "\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        x = max(nums)\n",
    "        ba = 0\n",
    "        for n in nums:\n",
    "            bn = 31\n",
    "            while n >> bn:\n",
    "                bn -= 1\n",
    "            ba = max(bn,ba)\n",
    "        class tire:\n",
    "            def __init__(self):\n",
    "                self.next=[None]*2\n",
    "                self.p = 0\n",
    "                self.e = 0\n",
    "            \n",
    "            def insert(self,next_num:int):\n",
    "\n",
    "                self.p += 1\n",
    "                if self.next[next_num] is None:\n",
    "                    self.next[next_num] = tire()\n",
    "                return self.next[next_num]\n",
    "\n",
    "\n",
    "            def find(self,next_num:int)->int:\n",
    "                if self.next[next_num] is None:\n",
    "                    return False\n",
    "                return True\n",
    "        root = tire()\n",
    "        for n in nums:\n",
    "            b = ba\n",
    "            p = root\n",
    "            while b >= 0:\n",
    "                p = p.insert((n >> b) & 1)\n",
    "                b-=1\n",
    "            p.e += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for n in nums:\n",
    "            b = ba\n",
    "            t = 0\n",
    "            i = root\n",
    "            while b >= 0:\n",
    "                if (n >> b) & 1:\n",
    "                    if i.find(0):\n",
    "                        t = (t<<1)+1\n",
    "                        i = i.next[0]\n",
    "                    else:\n",
    "                        t = t << 1\n",
    "                        i = i.next[1]\n",
    "                else:\n",
    "                    if i.find(1):\n",
    "                        t = (t<<1)+1\n",
    "                        i = i.next[1]\n",
    "                    else:\n",
    "                        t = t<<1\n",
    "                        i = i.next[0]\n",
    "                b -= 1\n",
    "\n",
    "            ans = max(ans,t)\n",
    "\n",
    "\n",
    "\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "\n",
    "        trie = Trie()\n",
    "        result = 0\n",
    "        for num in nums:\n",
    "            trie.insert(num)\n",
    "            maxxor = trie.findmaxxor(num)\n",
    "            result = max(result,maxxor)\n",
    "        return result\n",
    "class TrieNode:\n",
    "    def __init__(self) -> None:\n",
    "        self.child = [None,None]\n",
    "        \n",
    "class Trie:\n",
    "    def __init__(self) -> None:\n",
    "        self.root = TrieNode()\n",
    "        self.bitnum = 30\n",
    "\n",
    "    def insert(self,num):\n",
    "        cur = self.root\n",
    "        for i in range(self.bitnum , -1, -1):\n",
    "            bit = (num >> i ) & 1\n",
    "            if  not cur.child[bit]:\n",
    "                cur.child[bit] = TrieNode()\n",
    "            cur = cur.child[bit]\n",
    "    \n",
    "    def findmaxxor(self,num):\n",
    "        cur = self.root\n",
    "        maxval = 0\n",
    "        for i in range(self.bitnum , -1, -1):\n",
    "            bit = (num >> i) & 1\n",
    "            if cur.child[bit ^ 1]:\n",
    "                cur = cur.child[bit ^ 1]\n",
    "                maxval += 2**i\n",
    "            else:\n",
    "                cur = cur.child[bit]\n",
    "        return maxval"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.val=[None,None]\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums) -> int:\n",
    "        head=Node()\n",
    "        self.createtree(head,nums)\n",
    "        max=0\n",
    "        for num in nums:\n",
    "            ptr=head\n",
    "            now=0\n",
    "            for i in range(30,-1,-1):\n",
    "                k=(num>>i)&1\n",
    "                if ptr.val[1-k]!=None:\n",
    "                    now+=pow(2,i)\n",
    "                    ptr=ptr.val[1-k]\n",
    "                else:\n",
    "                    ptr = ptr.val[k]\n",
    "            if now>max:\n",
    "                max=now\n",
    "        return max\n",
    "\n",
    "    def createtree(self,head,nums):\n",
    "        for num in nums:\n",
    "            ptr = head\n",
    "            for i in range(30,-1,-1):\n",
    "                k=(num>>i)&1\n",
    "                if ptr.val[k]==None:\n",
    "                    ptr.val[k]=Node()\n",
    "                ptr=ptr.val[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "\n",
    "        trie = Trie()\n",
    "        result = 0\n",
    "        for num in nums:\n",
    "            trie.insert(num)\n",
    "            maxxor = trie.findmaxxor(num)\n",
    "            result = max(result,maxxor)\n",
    "        return result\n",
    "class TrieNode:\n",
    "    def __init__(self) -> None:\n",
    "        self.child = [None,None]\n",
    "        \n",
    "class Trie:\n",
    "    def __init__(self) -> None:\n",
    "        self.root = TrieNode()\n",
    "        self.bitnum = 30\n",
    "\n",
    "    def insert(self,num):\n",
    "        cur = self.root\n",
    "        for i in range(self.bitnum , -1, -1):\n",
    "            bit = (num >> i ) & 1\n",
    "            if  not cur.child[bit]:\n",
    "                cur.child[bit] = TrieNode()\n",
    "            cur = cur.child[bit]\n",
    "    \n",
    "    def findmaxxor(self,num):\n",
    "        cur = self.root\n",
    "        maxval = 0\n",
    "        for i in range(self.bitnum , -1, -1):\n",
    "            bit = (num >> i) & 1\n",
    "            if cur.child[bit ^ 1]:\n",
    "                cur = cur.child[bit ^ 1]\n",
    "                maxval += 2**i\n",
    "            else:\n",
    "                cur = cur.child[bit]\n",
    "        return maxval"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.child = [None]*2\n",
    "        self.isend = -1 \n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "    def insert(self,num):\n",
    "        cur = self.root\n",
    "        for i in range(31,-1,-1):\n",
    "            b = (num >> i) & 1\n",
    "            if not cur.child[b]:\n",
    "                cur.child[b] = TrieNode()\n",
    "            cur = cur.child[b]\n",
    "        cur.isend = num\n",
    "    \n",
    "    def find(self,num):\n",
    "        cur = self.root\n",
    "        for i in range(31,-1,-1):\n",
    "            b = (num >> i) & 1 ^ 1\n",
    "            if not cur.child[b]:\n",
    "                if not cur.child[b^1]:\n",
    "                    return num^cur.isend\n",
    "                cur = cur.child[b^1]\n",
    "            else:\n",
    "                cur = cur.child[b]\n",
    "        return cur.isend^num\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        # 扫描一遍得到数组当作两个数最大的异或值\n",
    "        trie = Trie()\n",
    "        res = 0 \n",
    "        for num in nums:\n",
    "            trie.insert(num)\n",
    "            res = max(res,trie.find(num))\n",
    "        return res\n",
    "        # 前缀树\n",
    "        # 最长完全不同前缀是什么？\n",
    "         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie_Node:\n",
    "    def __init__(self):\n",
    "        self.next = [None,None]\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = Trie_Node()\n",
    "\n",
    "    def insert(self, nums):\n",
    "        self.max_len = len(str(bin(max(nums))[2:]))\n",
    "        for num in nums:\n",
    "            temp = str(bin(num)[2:].zfill(self.max_len))\n",
    "            node = self.root\n",
    "            for p in temp:\n",
    "                if p == '0':\n",
    "                    if node.next[0] == None:\n",
    "                        node.next[0] = Trie_Node()\n",
    "                        node = node.next[0]\n",
    "                    else:\n",
    "                        node = node.next[0]\n",
    "                else:\n",
    "                    if node.next[1] == None:\n",
    "                        node.next[1] = Trie_Node()\n",
    "                        node = node.next[1]\n",
    "                    else:\n",
    "                        node = node.next[1]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        Trie_tree = Trie()\n",
    "        Trie_tree.insert(nums)\n",
    "        maxXOR=0\n",
    "        for num in nums:\n",
    "            XOR = 0\n",
    "            temp = str(bin(num)[2:].zfill(Trie_tree.max_len))\n",
    "            node = Trie_tree.root\n",
    "            for bit in temp:\n",
    "\n",
    "\n",
    "                if bit == '0':\n",
    "                    if node.next[1] != None:\n",
    "                        XOR = 2 * XOR + 1\n",
    "                        node = node.next[1]\n",
    "                    elif node.next[0] != None:\n",
    "                        XOR = 2 * XOR\n",
    "                        node = node.next[0]\n",
    "\n",
    "                if bit == '1':\n",
    "                    if node.next[0] != None:\n",
    "                        XOR = 2 * XOR + 1\n",
    "                        node = node.next[0]\n",
    "                    elif node.next[1] != None:\n",
    "                        XOR = 2 * XOR\n",
    "                        node = node.next[1]\n",
    "\n",
    "                if node.next[0] == None and node.next[1] == None:\n",
    "                    maxXOR = max(maxXOR, XOR)\n",
    "                    continue\n",
    "        return maxXOR\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.rt={}\n",
    "        self.ed='#'\n",
    "    def add(self, wd):\n",
    "        nd=self.rt\n",
    "        for c in wd:\n",
    "            nd=nd.setdefault(c,{})\n",
    "        nd[self.ed]={}\n",
    "    def find(self, wd):\n",
    "        nd=self.rt\n",
    "        for c in nd:\n",
    "            if c not in nd:\n",
    "                return False\n",
    "            nd=nd[c]\n",
    "        return self.ed in nd\n",
    "    def finddiff(self, wd):\n",
    "        ans=0\n",
    "        nd=self.rt\n",
    "        dd={'0':'1', '1':'0'}\n",
    "        for i, cc in enumerate(wd):\n",
    "            if dd[cc] in nd:\n",
    "                nd=nd[dd[cc]]\n",
    "                ans+=(1<<(31-1-i))\n",
    "            else:\n",
    "                nd=nd[cc]\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        tree=Trie()\n",
    "        ans=0\n",
    "        print(tree.rt)\n",
    "        for c in nums:\n",
    "            wd=list(bin(c)[2:].zfill(31))\n",
    "            tree.add(wd)\n",
    "            ans=max(ans, tree.finddiff(wd))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.rt={}\n",
    "        self.ed='#'\n",
    "    def add(self, wd):\n",
    "        nd=self.rt\n",
    "        for c in wd:\n",
    "            nd=nd.setdefault(c,{})\n",
    "        nd[self.ed]={}\n",
    "    def find(self, wd):\n",
    "        nd=self.rt\n",
    "        for c in nd:\n",
    "            if c not in nd:\n",
    "                return False\n",
    "            nd=nd[c]\n",
    "        return self.ed in nd\n",
    "    def finddiff(self, wd):\n",
    "        ans=0\n",
    "        nd=self.rt\n",
    "        dd={'0':'1', '1':'0'}\n",
    "        for i, cc in enumerate(wd):\n",
    "            if dd[cc] in nd:\n",
    "                nd=nd[dd[cc]]\n",
    "                ans+=(1<<(31-1-i))\n",
    "            else:\n",
    "                nd=nd[cc]\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        tree=Trie()\n",
    "        ans=0\n",
    "        print(tree.rt)\n",
    "        for c in nums:\n",
    "            wd=list(bin(c)[2:].zfill(31))\n",
    "            tree.add(wd)\n",
    "            ans=max(ans, tree.finddiff(wd))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.T = {}\n",
    "    \n",
    "    def append(self, s):\n",
    "        cur = self.T\n",
    "        for i in s:\n",
    "            if i not in cur:\n",
    "                cur[i] = {}\n",
    "            cur = cur[i]\n",
    "        cur['isEnd'] = 0\n",
    "    \n",
    "    def X(self, s):\n",
    "        cur = self.T\n",
    "        res = ''\n",
    "        for i in s:\n",
    "            if (i == '1' and '0' in cur) or (i == '0' and '1' in cur):\n",
    "                res += '1'\n",
    "                cur = cur[str(int(i)^1)]\n",
    "            else:\n",
    "                res += '0'\n",
    "                cur = cur[i]\n",
    "        return int(res, 2)\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        T = Trie()\n",
    "        l = max(len(bin(i)) for i in nums)\n",
    "        bins = ['0' * (l - len(bin(i))) + bin(i)[2:] for i in nums]\n",
    "        for i in bins:\n",
    "            T.append(i)\n",
    "        res = 0\n",
    "        for i in bins:\n",
    "            res = max(res, T.X(i))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "首先将数据补充为32位，\n",
    "然后构建一颗前缀树，从高位到低位\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.next = {}\n",
    "        self.end = False\n",
    "\n",
    "\n",
    "class Tree:\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "\n",
    "    # 将数据都转换为32位\n",
    "    def change(self, num):\n",
    "        bin_num = bin(num)[2:]\n",
    "        bin_num = (32 - len(bin_num)) * '0' + bin_num\n",
    "        return bin_num\n",
    "\n",
    "    def add(self, num):\n",
    "        cur = self.root\n",
    "\n",
    "        bin_num = self.change(num)\n",
    "        # 从高位到低位加入\n",
    "        for i in bin_num:\n",
    "            if i not in cur.next:\n",
    "                cur.next[i] = Node()\n",
    "            cur = cur.next[i]\n",
    "\n",
    "    def search(self, num):\n",
    "        bin_num = self.change(num)\n",
    "        cur = self.root\n",
    "        res = 0\n",
    "\n",
    "        for i in bin_num:\n",
    "            flag = 0\n",
    "            tar = '0' if i == '1' else '1'\n",
    "            if tar in cur.next:\n",
    "                cur = cur.next[tar]\n",
    "                flag = 1\n",
    "            else:\n",
    "                cur = cur.next[i]\n",
    "\n",
    "            res <<= 1\n",
    "            res |= flag\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        tree = Tree()\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            tree.add(num)\n",
    "            r = tree.search(num)\n",
    "            res = max(r, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.next = {}\n",
    "        self.num = None\n",
    "    \n",
    "    def insert(self, num):\n",
    "        root = self\n",
    "        for i in range(31, -1, -1):\n",
    "            d = num >> i & 1\n",
    "            if d not in root.next:\n",
    "                root.next[d] = Trie()\n",
    "            root = root.next[d]\n",
    "        root.num = num\n",
    "\n",
    "    def search(self, num):\n",
    "        root = self\n",
    "        for i in range(31, -1, -1):\n",
    "            d = num >> i & 1\n",
    "            xor_d = d ^ 1\n",
    "            if xor_d in root.next:\n",
    "                root = root.next[xor_d]\n",
    "            else:\n",
    "                root = root.next[d]\n",
    "        return root.num\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # https://leetcode.cn/problems/ms70jA/description/comments/1183379\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        tree = Trie()\n",
    "        for num in nums:\n",
    "            tree.insert(num)\n",
    "        for num in nums:\n",
    "            xor_num = tree.search(num)\n",
    "            result = max(result, xor_num ^ num)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Tier:\n",
    "    def __init__(self):\n",
    "        self.nodes = {}\n",
    "        self.num = None\n",
    "    \n",
    "    def insert(self, num):\n",
    "        node = self\n",
    "        for i in range(31, -1, -1):\n",
    "            d = num >> i & 1\n",
    "            if d not in node.nodes:\n",
    "                node.nodes[d] = Tier()\n",
    "            node = node.nodes[d]\n",
    "        node.num = num\n",
    "          \n",
    "    def XOR_(self, num):\n",
    "        node = self\n",
    "        for i in range(31, -1, -1):\n",
    "            d = num >> i & 1\n",
    "            xor_d = d ^ 1\n",
    "            if xor_d in node.nodes:\n",
    "                node = node.nodes[xor_d]\n",
    "            else:\n",
    "                node = node.nodes[d]\n",
    "        return node.num\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        def to_bin(num):\n",
    "            ret = ''\n",
    "            for i in range(32):\n",
    "                k = num >> i & 1\n",
    "                ret += str(k)\n",
    "            return ret[::-1]\n",
    "        \n",
    "        tree = Tier()\n",
    "        for num in nums:\n",
    "            tree.insert(num)\n",
    "        result = 0\n",
    "        for num in nums:\n",
    "            xor_num = tree.XOR_(num)\n",
    "            result = max(result, xor_num ^ num)\n",
    "        return result"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
